#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>
using namespace std;

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> Q;
        for (int i = 0; i < stones.size(); ++i)
        {
            Q.push(stones[i]);
        }
        while (Q.size() > 1)
        {
            int top1 = Q.top();
            Q.pop();
            int top2 = Q.top();
            Q.pop();
            if (top1 != top2) Q.push(top1 - top2);
        }
        if (Q.size() == 1) return Q.top();
        else return 0;
    }

    long long maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf_gcd(n + 1);
        vector<long long> suf_lcm(n + 1);
        suf_lcm[n] = 1;
        for (int i = n - 1; i >= 0; --i)
        {
            suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i]);
            suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i]);
        }
        long long ans = suf_gcd[0] * suf_lcm[0];
        long long pre_lcm = 1;
        int pre_gcd = 0;
        for (int i = 0; i < n; ++i)
        {
            ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]));
            pre_gcd = gcd(pre_gcd, nums[i]);
            pre_lcm = lcm(pre_lcm, nums[i]);
        }
        return ans;
    }


    struct KVcom
    {
        bool operator()(const pair<string, int> p1, const pair<string, int> p2)
        {
            return p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> mp;
        for (auto w : words)
        {
            ++mp[w];
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, KVcom> Q(mp.begin(), mp.end());
        vector<string> ans;
        for (int i = 0; i < k; ++i)
        {
            ans.push_back(Q.top().first);
            Q.pop();
        }
        return ans;
    }

    vector<vector<int>> ret;
    vector<int> path;
    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            ret.push_back(path);
            return;
        }
        path.push_back(nums[pos]);
        dfs(nums, pos + 1);
        path.pop_back();
        dfs(nums, pos + 1);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
       
    };

    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return 1;
        int min_depth = INT_MAX;
        if (root->left)
            min_depth = min(minDepth(root->left), min_depth);
        if (root->right)
            min_depth = min(minDepth(root->right), min_depth);
        return min_depth + 1;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        if (root->left == nullptr && root->right == nullptr) return targetSum == root->val;
        return hasPathSum(root->left, targetSum - root->val) ||
            hasPathSum(root->right, targetSum - root->val);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        else if (p == nullptr || q == nullptr) return false;
        else if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(q->right, p->right);
    }
};

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> Q;
    int _k;
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for (int i = 0; i < nums.size(); ++i)
        {
            Q.push(nums[i]);
            if (Q.size() > k) Q.pop();
        }

    }

    int add(int val) {
        Q.push(val);
        if (Q.size() > _k) Q.pop();
        return Q.top();
    }

};